# -*- coding: utf-8 -*-
"""
    Time    : 2021/1/7 12:06 下午
    Author  : Thinkgamer
    File    : 021-合并两个有序链表.py
    Desc    : https://leetcode-cn.com/problems/merge-two-sorted-lists/
"""
"""
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
"""

class ListNode:
	def __init__(self, val=0, next=None):
		self.val = val
		self.next = next


# 40ms 88.87% | 14.6mb 20.31%
def merge_two_lists(l1, l2):
	head = ListNode()
	other = head
	while l1 and l2:
		if l1.val < l2.val:
			other.next = l1
			l1 = l1.next
			other = other.next
		else:
			other.next = l2
			l2 = l2.next
			other = other.next
	while l1 or l2:
		while l1:
			other.next = l1
			l1 = l1.next
			other = other.next

		while l2:
			other.next = l2
			l2 = l2.next
			other = other.next
	return head.next


# 创建两个有序链表
one = ListNode(1)
two = ListNode(2)
three = ListNode(3)
one.next = two
two.next = three

three1 = ListNode(3)
four = ListNode(4)
three1.next = four
head = merge_two_lists(one, three1)
while head:
	print(head.val)
	head = head.next
